/*
 * @Description: 
 * @Version: 2.0
 * @Author: xuchaoxin
 * @Date: 2021-03-07 18:15:45
 * @LastEditors: xuchaoxin
 * @LastEditTime: 2021-03-07 20:17:17
 */
//（174）谢尔（Shell）排序
/*排序思想：进行多趟排序。
本文较为详细的说明了希尔排序的算法及其具体的操作过程,但还是建议先对直接插入排序有较为深刻的了解后在阅读本文(阅读过程中可以对比这看直接插入排序和本文的希尔排序)
(该算法包含了三重循环:第一重循环是为了让gap能够取不同的值;
内层的for则是为了对各个gap下所得到的分组子序列并行执行插入排序

在每趟排序时，按照给定的元素位置增量对元素进行逻辑组的划分，

在每个逻辑组内并行地对元素进行直接插入排序。(既然时基于直接插入排序,那么请务必对直接插入排序做的很熟练(shu'lian),不然怎么指望对shell排序熟练(甚至只是理解代码),可以相互参照对比学习两种算法)

每趟排序所用的位置增量随着算法进行而减少，直到最后一趟，所有元素均分在同一组。(此时只有一组)

因此，Shell排序也称为“缩减增量排序”。*/
#include <iostream>
/**********************************************************
使用Shell增量，对数组r[]中的n个元素进行Shell排序
	*********************************************************/
void shellSort(int r[], /* 保存待排序序列的数组 */
               int n)   /* 原待排序列元素个数 */
{
    int i,   /* 索引变量i,用来表示各个逻辑分组中,待被插入到有序区元素的索引(各无序区中各元素的索引) */
        j,   /* 索引变量j,用来表示各个逻辑分组中,有序区元素的索引,用于构成r[j-k*gap](k=0,1,...和tmp(待插入元素)进行比较*/
        gap; /* 用于划分逻辑分组的增量 */
             /* 关于IDE:变量说明(文档)放在分隔符(,或;)之后才能智能提示 */
    int tmp; /* 用于保存待插入元素(作用如同直接插入排序中的临时变量一样) */

    /* gap初始化为n */
    for (gap = n; gap > 0; gap /= 2) /* // 用于分配Shell增量序列里的元素：欲让gap=N/2, N/4,..., 1时进入循环;依次将数列分为gap_i个组(gap_i逐渐减小至1,数列所划分的逻辑组的数量也相应的减少至1组(此时的shell排序即为直接插入排序)
    而第i趟排序所划分的每个组所含有的元素数目为:n/gap_i 
    注意,各个逻辑组中的元素的分布在原序列中不是连续的*/
    {
        /*对根据当前gap所分成的各个组(子序列)进行并行执行的直接插入排序*/
        for (i = gap; /* i初始化为第一个逻辑分组中第一个要被插入的元素(无序区中的第一个元素,而不是该逻辑分组的第一个元素) */
             i < n;   /* 知道原序列中最后一个一个元素被排序(插入到对应分组内的正确位置上) */
             i++)     /* i=gap,gap+1,...,n-1 ;//i增加1,就是切换到下一个逻辑分组序列进行排序;在这gap=gap_i个分组间来回循环切换*/
        {
            /* 以增量gap对元素进行分组(只是想法上的分组,并不直接体现在代码上(存储结构上)，并排序,
        并且,每次排序都是几个子序列一同开始(每次经过for都为某个序列的有序部分增加一个元素,而不是先把某一个序列一次性排完才取排下一个子序列 */
            /* 把r[i] 插入到组中的恰当位置，使得下面的元素序列有序：
            (r[j], r[j-gap], r[j-2*gap]...) */
            tmp = r[i]; /* 待排序元素r[i]暂存到tmp */

            /* 依次检查同一逻辑分组中的元素:r[j-gap], r[j-2*gap]...与待插入元素tmp的关系，若tmp小于当前位置的元素，则把当前位置元素r[j-n*gap]往后移gap个位置 */
            /* 执行直接插入排序,通过j-=gap来计算逻辑分组中逻辑相邻的下一个元素在原始序列中的索引 */
            /*关于j>=gap:j是索引变量,我们需要访问的最小索引 j-gap >= 0,故j>=gap,否则r[j-gap]会出错*/
            for (j = i;                        /* 这里j的初始化:i>=gap,所以j=i>=gap;j_max=i_max=n-1 */
                 j >= gap && tmp < r[j - gap]; /* &&是短路与,j<gap的话,就不会执行r[j-gap],故是安全的 */
                 j -= gap)
            {
                r[j] = r[j - gap]; /*location_1处 ;将相对于当前元素的前gap个间隙位置的元素r[j-gap]后移并覆盖到当前位置j处的元素
                如此,r[j-gap]的值就可以被更小的值所覆盖*/
            }                      /*离开此for循环时,j比location_1处又小了(即前进了)gap*/
            /* 当第一次成立tmp>r[j-gap]时或j-gap<0之前tmp<r[j-gap]成立,触发tmp的插入操作 */
            r[j] = tmp; /*location_2 (可以将保存在tmp中的待插入元素插入到(对应分组)正确位置上)*/
        }
    }
}
int main()
{
    int a[] = {3, 5, 1, 0, 9};
    shellSort(a, 5);
    for (int i = 0; i < 5; i++)
    {
        printf("%d ", a[i]);
    }
}
